/**
 * https://leetcode.cn/problems/numbers-with-repeated-digits/submissions/568715135/
 * 1012. 至少有 1 位重复的数字
 * difficulty 陈贝纯 2024.09.28
 * 数位dp
 */

class Solution {
public:
    bool visit[10];
    int rep;
    int digit=0;
    int sum=0;
    int r;
    void dfs(int num,int n){
        for(int i=0;i<10;++i){
            if(!visit[i]){
                if(n<digit){
                    visit[i]=true;
                    dfs(num*10+i,n+1);
                    visit[i]=false;
                }
                if(n==digit&&!visit[i]){
                    if(num<rep||(num==rep&&i<=r))
                        sum++;
                    else
                    return;
                }
                }
            }
    }
    int numDupDigitsAtMostN(int n) {
        if(n<=9)
        return 0;
        r=n%10;
        rep=n/10;
        int m=n;
        while(m/10){
            digit++;
            m/=10;
        }
        int d=9;
        int num=9;
        for(int i=0;i<digit;++i){
            sum+=num;
            num*=d;
            d--;
        }
        num/=9;
        sum+=(m-1)*num;
        visit[m]=true;
        dfs(m,1);
        return n-sum;
    }
};